class Node:
    def __init__(self, p = None):
        self.parent = p
        self.times = 0
        self.tokens = []

    def toString(self) -> str:
        r = ''
        for t in self.tokens:
            if isinstance(t, str):
                r += t
            else:
                r += t.toString()
        return r * self.times

class Solution:
    def decodeString(self, s: str) -> str:
        root = Node()
        currNode = root
        for (v, t) in self.lex(s):
            if t == 'NUM':
                if currNode.times == 0:
                    currNode.times = v
                else:
                    newNode = Node()
                    newNode.times = v
                    newNode.parent = currNode
                    currNode.tokens.append(newNode)
                    currNode = newNode
            elif t == 'LB':
                pass
            elif t == 'SEG':
                currNode.tokens.append(v)
            elif t == 'RB':
                currNode = currNode.parent
        return root.toString()

    def lex(self, s:str):
        yield (1, 'NUM')
        yield ('[', 'LB')
        i, n = 0, len(s)
        while i < n:
            cc = s[i]
            if cc == '[':
                yield ('[', 'LB')
                i += 1
            elif cc == ']':
                yield (']', 'RB')
                i += 1
            elif cc in "0123456789":
                nc = cc
                t = ""
                while i < n and nc in "0123456789":
                    t += nc
                    i += 1
                    if i < n:
                        nc = s[i]
                yield (int(t), 'NUM')
            else:
                nc = cc
                t = ""
                while i < n and nc not in "0123456789" and nc != '[' and nc != ']':
                    t += nc
                    i += 1
                    if i < n:
                        nc = s[i]
                yield (t, 'SEG')
        yield (']', 'RB')

solu = Solution()
# print([i for i in solu.lex("2[abc]3[cd]ef")])
# print(solu.decodeString("2[abc]3[cd]ef"))
# print(solu.decodeString("3[a2[c]]"))
# print(solu.decodeString("3[a]2[bc]"))

print([i for i in solu.lex("23[a]56[b]89[c]")])
# print(solu.decodeString("23[a]56[b]89[c]"))